Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 11336 - DRM / drm.cpp
bloba201f5b1c1a9c16f6f53124c62b30f608caa9d02
1 #include <iostream>
2 #include <map>
3 #include <vector>
4 #include <string>
5 #include <sstream>
6 #include <set>
8 using namespace std;
10 typedef string node;
11 typedef pair<node, node> edge;
12 typedef map<node, vector<node> > graph;
14 bool dfs(node v, node destiny, set<node> visited, const graph &g, const set<node> &forbidden){
15 vector<node> neighbors = (*(g.find(v))).second;
16 for (int i=0; i<neighbors.size(); ++i){
17 if (neighbors[i] == destiny) return true;
18 if (!(visited.count(neighbors[i])) && !(forbidden.count(neighbors[i]))){
19 set<node> temp = visited;
20 temp.insert(v);
21 if (dfs(neighbors[i], destiny, temp, g, forbidden)){
22 return true;
26 return false;
29 bool validate(edge e, const graph &g, const set<node> &forbidden){
30 set<node> visited;
31 return (dfs(e.first, e.second, visited, g, forbidden));
34 int main(){
35 string name1, name2;
36 while (getline(cin, name1) && name1 != "END"){
37 graph g;
38 set<node> forbidden;
39 string line;
40 vector<edge> streets;
41 while (getline(cin, line) && line != "* * *"){
42 stringstream sin;
43 sin << line;
44 edge e;
45 sin >> e.first >> e.second;
46 streets.push_back(e);
47 forbidden.insert(e.first);
48 forbidden.insert(e.second);
51 getline(cin, name2);
52 while (getline(cin, line) && line != "* * *"){
53 stringstream sin;
54 sin << line;
55 edge e;
56 sin >> e.first >> e.second;
57 vector<node> v;
58 if (g.count(e.first) == 0){
59 g[e.first] = v;
61 if (g.count(e.second) == 0){
62 g[e.second] = v;
64 g[e.first].push_back(e.second);
65 g[e.second].push_back(e.first);
68 //Terminé la lectura
69 for (set<node>::iterator it = forbidden.begin(); it != forbidden.end(); ++it){
70 if (g.count((*it)) == 0){
71 cout << "NO: " << name2 <<" is not a more detailed version of " << name1 << endl;
72 continue;
75 bool impossible = false;
76 for (int i=0; i<streets.size(); ++i){
77 if (!validate(streets[i], g, forbidden)){
78 impossible = true;
79 break;
82 if (impossible){
83 cout << "NO: " << name2 <<" is not a more detailed version of " << name1 << endl;
84 }else{
85 cout << "YES: " << name2 <<" is a more detailed version of " << name1 << endl;
88 return 0;